#include<vector>
using namespace std;
class Solution {
    int ret = 0;
    int dx[2] = { 0,1 };
    int dy[2] = { 1,0 };
    vector<vector<bool>>check;
    int row, col;
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        row = m, col = n;
        check = vector<vector<bool>>(row, vector<bool>(col, false));
        dfs(0, 0, cnt);
        return ret;
    }

    void dfs(int i, int j, int cnt) {
        ret++;
        check[i][j] = true;
        for (int k = 0; k < 2; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x < row && y < col && (portSum(x) + portSum(y)) <= cnt && check[x][y] == false) {
                dfs(x, y, cnt);
            }
        }
    }
    int portSum(int x) {
        int sum = 0;
        while (x) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    }
};